/**
 * 611. 有效三角形的个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
 */

#include "common.h"

class Solution
{
public:
    int triangleNumber(std::vector<int> &nums)
    {
        int sz = nums.size();
        if (sz < 3)
        {
            return 0;
        }
        sort(nums.begin(), nums.end(), [](int x, int y)
             { return x < y; }); // O(n*logn)

        int ret = 0;
        for (int i = sz - 1; i > 0; --i)
        {
            int left = 0;
            int right = i - 1; // left 表示 较小的后面的数  right 表示 第二个大的数
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    --right;
                }
                else
                {
                    ++left;
                }
            }
        }
        return ret;
    }
};